\documentclass[a4paper,12pt]{article}

\usepackage[T2A]{fontenc} 
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{listings}
\usepackage[dvips]{graphicx}
\usepackage{indentfirst}
\usepackage{color}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{geometry}
\geometry{left=1.5cm}
\geometry{right=1.5cm}
\geometry{top=1cm}
\geometry{bottom=2cm}

\graphicspath{{images/}}

\begin{document}
\sloppy

\lstset{
	basicstyle=\small,
	stringstyle=\ttfamily,
	showstringspaces=false,
	columns=fixed,
	breaklines=true,
	numbers=right,
	numberstyle=\tiny
}

\newtheorem{Def}{Определение}[section]
\newtheorem{Th}{Теорема}
\newtheorem{Lem}[Th]{Лемма}
\newenvironment{Proof}
	{\par\noindent{\bf Доказательство.}}
	{\hfill$\scriptstyle\blacksquare$}
\newenvironment{Solution}
	{\par\noindent{\bf Решение.}}
	{\hfill$\scriptstyle\blacksquare$}


\begin{flushright}
	Кринкин М. Ю. группа 504 (SE)
\end{flushright}

\section{Домашнее задание 1}

\paragraph{Задание 1.} Докажите, что если простой связный граф имеет ровно две вершины, при удалении которых граф не теряет связность, то это граф простой путь.
\begin{Solution}
Очевидно, что граф имеющий более двух висячих вершин не является путем и не подходит под условия задачи. Удаление любой вершины из графа не содержащего висячих вершин не меняет его связности, и такой граф не яляется путем, т. к. содержит циклы. Граф имеющий только одну висячую вершину, является точкой и не подходит под условие, либо яляется графом с циклом (циклами), покажем, что в этом графе есть более двух вершин, удаление которых не нарушает связность.

Выберем один цикл графа, висячая вершина соединена как минимум с одной вершиной входящей в выбранный цикл путем таким, что только его последняя вершина принадлежит выбранному пути. В цикле как минимум 3 вершины, любую вершину, кроме той которая связана путем с висячей можно удалить не потеряв связности, а значит имеется как минимум 3 вершины, которые можно удалить не нарушив связность. Теперь рассмотрим последний случай, когда в графе ровно 2 висячие вершины, этот граф либо является деревом и одновременно путем, либо содержит циклы и не является деревом, по аналогичной предыдущему рассуждению схеме, можно проложить к выделенному циклу два пути от висячих вершин, все остальные вершины цикла могут быть удалены, т. е. опять же существуют как минимум 3 вершины, которые можно удалить не нарушив связность.

Таким образом показано, что единственный случай когда имеются ровно две вершины, которые можно удалить не нарушив связность, является случай, когда граф не содержит циклов, и имеет ровно две висячие вершины, т. е. является путем.
\end{Solution}

\paragraph{Задание 2.} В связном графе степени всех вершин четны. Докажите, что при удалении любого ребра он сохраняет связность.
\begin{Solution}
Пусть это не так, т. е. при удалении одного ребра мы получили две компоненты связности, причем в каждой из них ровно по одной вершине, степень которых нечетна (удалили одно ребро, степень вершин связанных им уменьшилась на 1, т. е. стала нечетной), но это не возможно, так как внутри одной компоненты связности сумма степеней вершин четна и равна удвоенному количеству ребер.
\end{Solution}

\paragraph{Задание 3.} В связном графе степень каждой вершины не меньше k, докажите, что в графе найдется простой цикл содержащий не менее k+1 вершины
\begin{Solution}
Будем последовательно обходить вершины графа и отмечать их номерами начиная с единицы. Из каждой ершины можно переходить только в непомеченную номером вершину, оставливаем просмотр, когда придем в вершину у которой больше нет непомеченных соседей. За каждый шаг мы отмечаем одну вершину и следовательно алгоритм конечен (хотя, возможно, не просматривает всех вершин графа). Так как рассматриаемая вершина не имеет соседей, то помечено как минимум $k$ вершин, и по алгоритму они образуют путь, рассматриваемая вершина как минимум $k+1$ в этом пути, а добавив в этот путь ребро от $k+1$ вершины к смежной вершине с минимальным номером получаем простой цикл, с как минимум $k+1$ вершиной.
\end{Solution}

\paragraph{Задание 4.} Докажите, что из произвольного сязного графа можно выкинуть вершину и инцедентные ребра, так чтобы граф остался связным.
\begin{Solution}
Для дерева утверждение очевидно, так как дерево содержит висячие вершины. Из любого графа можно получить дерево, последовательно находя и удаля по ребру из каждого цикла. Вершина, которая после такого удаления осталась висящей, может быть удалена вместе со всеми инцедентными ребрами в исходном графе не нарушая его связность.
\end{Solution}

\paragraph{Задание 5.} Докажите, что в любом графе есть две вершины одинаковой степени.
\begin{Solution}
Пусть это не так, тогда, если в графе есть $n$ вершин, и все с разной степенью, то их степени равны $(n-1), (n-2), ... , 2, 1, 0$, но это не возможно, так как вершина со степенью $n-1$ связана со всеми остальными вершинами, и не может существовать вершины со стопенью 0, т. е. пришли к противоречию.
\end{Solution}

\paragraph{Задание 6.} Множество вершин графа называется доминирующим, если любая не входящая в него вершина смежна хотябы с одной вершиной этого множества. Докажите, что количество доминирующих множеств в любом графе нечетно.
\begin{Solution}
Пусть теорема справедлива для связных графов, покажем, что она выполнится и для не связных. Доказательство этого факта вытекает из того, что количество доминирующих множеств для несвязного графа получается перемножением количества доминирующих множеств его компонент связности, а значит так же яляется нечетным. Покажем теперь, что теорема справедлива для связных графов. Доказательство будем производить индукцией по числу вершин. База индукции очевидна, например для связного графа из двух вершин, или из трех (для графа из четырех вершин, все сложнее, так как таких графов уже больше и число доминирующих множеств также больше). Пусть теперь для всех связных графов с числом вершин меньшим или равным $l$ утверждение теоремы справделиво. Добавим в связный граф $G$ с $l$ вершинами одну новую вершину $x_n$, соединенную с вершинами $G$ произвольными ребрами. В новом графе $\tilde G$ будут доминирующие множества вершин следующих классов:
\begin{enumerate}
\item Доминирующие множества, которые являлись доминирующими множествами в графе $G$ и включали вершины смежные с $x_n$ (т. е. добавление $x_n$ не меняет свойство доминируемости)

\item Доминирующие множества, полученные из предыдущего класса добавлением в них вершины $x_n$ (Добавление $x_n$ в любое доминирующее множество первого класса дает опять же доминирующее множество)

\item Доминирующие множества, полученные из доминирующих множеств графа $G$ не включавших вершины смежные с $x_n$ добавлением в них $x_n$ (т. е. множества переставшие быть доминирующими, после добавления $x_n$, добавив в них $x_n$ они преобразуются в доминирующие)

\item Доминирующие множества, не являвшиеся доминирующими множествами графа $G$, но ставшие таковыми после добавления в них вершины $x_n$ (т. е. множества вершин, которые не имели смежности с вершинами смежными $x_n$, но после добавления в них $x_n$ стали доминирующими)
\end{enumerate}
Множеств первого и второго класса равное количество, так как одни получены из других добавлением в каждое множество вершины $x_n$, обозначим это количество букой $m$. Множеств третьего класса $n$, множеств четвертого класса $k$. Количество доминирующих множеств в графе $\tilde G$ определяется соотношением $n + 2m + k$. Покажем, что $n+k$ - нечетно, это следует из того, что множества третьего и четвертого класса без вершины $x_n$ образуют множество доминирующих множеств графа полученного из $G$ удалением вершин смежных с $x_n$, а по индукционному предположению число доминирующих множеств в нем нечетно.
\end{Solution}

\paragraph{Задание 7.} Вершины связного графа покрашены в черный и белый цвета. Причем вершин черного цвета четное количество. Докажите, что можно выкинуть не более $n-1$ ребра так, чтобы в оставшемся графе все черные вершины имели бы нечетную степень, а белые четную.
\begin{Solution}
Из любого связного графа можно получить дерево удалением ребер, сделаем это с нашим графом. Выделим в нем корень, промежуточные уровни и листья. Отсечем от дерева все белые листья (удалим ведущие в них ребра) - отсеченные узлы имеют нулевую четную степень. Далее рассматриваем листья. Выбираем группу черных листьев таким образом, чтобы все они имели общего непосредстенного предка - общую смежную ершину не являющуюся листом. Каждая такая группа попадает под один из четырех случаев:
\begin{enumerate}
\item Число листьев в группе четно, общий предок - белая вершина. Всю группу отсоединяем от дерева целиком, в полученном подграфе все вершины удовлетворяют условию.

\item Число листьев в группе четно, общий предок - черная вершина. Листья группы отмечаем как помеченные, подграф оставляем в дереве до следующей итерации.

\item Число листьев в группе нечетно, общий предок - белая вершина. Листья группы отмечаем как просмотренные, подграф оставляем в дереве до следующей итерации.

\item Число листьев в группе нечетно, общий предок - черная вершина. Всю группу отсоединяем от дерева, в полученном подграфе только черные вершины и все имеют нечетную степень.
\end{enumerate}
Следующим шагом повторяем удаление белых листьев, если они появились, пока не остануться одни черные листья. Далее опять ищем общих непосредственных родителей непомеченных листьев и предков помеченных листьев (т. е. листья рассматривавшиеся на прошлой итерации более не рассматриваются, но рассматриваются их родители), опять же возможны те же самые четыре случая:
\begin{enumerate}
\item Число листьев и непомеченных не листьев с прошлой итерации в группе четно, общий предок - белая вершина. Всю группу отсоединяем от дерева целиком, в полученном подграфе все вершины удовлетворяют условию.

\item Число листьев и непомеченных не листьев с прошлой итерации в группе четно, общий предок - черная вершина. Листья и непомеченные не листья с прошлой итерации отмечаем как помеченные, подграф оставляем в дереве до следующей итерации.

\item Число листьев и непомеченных не листьев с прошлой итерации в группе нечетно, общий предок - белая вершина. Листья и непомеченные не листья с прошлой итерации отмечаем как просмотренные, подграф оставляем в дереве до следующей итерации.

\item Число листьев и непомеченных не листьев с прошлой итерации в группе нечетно, общий предок - черная вершина. Всю группу отсоединяем от дерева, в полученном подграфе все вершины удовлетворяют условию.
\end{enumerate}

Фактически мы отсоединяем от исходного дерева, построенные снизу вверх (от листьев к корню) поддеревья, в которых четное число черных вершин. Все поддеревья образуются так, чтобы при их отсоединении не потерять связность.

Алгоритм продолжается пока не останется белое дерево, либо пока дерево не станет пустым (оба условия эквивалентны, т.к. шаг удаления белых листьев преобразует белое дерево в пустой граф). Алгоритм очевидно конечен, кроме того черные вершины удаляются из графа четными "порциями", а значит невозможна ситуация, когда в дереве остались черные вершины, которые нельзя удалить, так как количество черных вершин четно, и может быть построенно поддерево, которое их включает и, следовательно, должно быть удалено по алгоритму.

\end{Solution}

\paragraph{Задание 8.} Из картона слеин кубик. Двое играют в следующую игру: за один ход разрешается разрезать вдоль любого ребра, которое еще не разрезано. Проигрывает тот, у кого кубик распадается на две части. Кто выиграет при правильной игре?
\begin{Solution}
Граф содержит 8 вершин и 12 ребер. Его остов содержит 7 ребер, следовательно, как только в кубе останется меньше семи ребер, он распадается на две части (граф теряет связность). Таким образом человек сделавший 6-ой разрез проигрывает.
\end{Solution}

\end{document}
